package leetcode.jianzhioffer;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-06 11:58
 **/
public class JianZhiOffer40 {

    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr, 0, arr.length - 1);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return Arrays.copyOfRange(arr, 0, k);
    }

    private void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int i = l;
        int j = r;
        int num = arr[l];
        while (i < j) {
            while (arr[j] >= num && i < j) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
            }
            while (arr[i] <= num && i < j) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
            }
        }
        arr[i] = num;
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }

}
